#include <vector>
#include <string>
#include <iostream>
#include <fstream>
#include <sstream>
#include <algorithm>
#include <iterator>
using namespace std;

class SimpleMap {
public:
	SimpleMap(const string filename) {
		string line;
		unsigned int lineNumber = 0;
		ifstream myfile (filename.c_str());

		if(myfile.is_open()) {
			while( myfile.good() ) {
				getline (myfile,line);
				if(line.size() > 0 && line[0] != '#') {
					switch(lineNumber) {
						case 0:
							width = strtol(line.c_str(), NULL, 10); break;
						case 1:
							height = strtol(line.c_str(), NULL, 10);
							size = width * height;
							graph.resize(size);
							blocked.resize(size);
							break;
						case 2:
							start = strtol(line.c_str(), NULL, 10);
							location = start;
							break;
						case 3:
							goal = strtol(line.c_str(), NULL, 10); break;
						default:
							vector<string> tokens;
							istringstream iss(line);
							copy(istream_iterator<string>(iss),
         							istream_iterator<string>(),
								back_inserter<vector<string> >(tokens));
							int index = strtol(tokens[0].c_str(), NULL, 10);
							for(unsigned int i = 1; i < tokens.size(); i++)
								graph[index].push_back(strtol(tokens[i].c_str(), NULL, 10));
							sort (graph[index].begin(), graph[index].end());
					};

					lineNumber++;
				}
			}
			myfile.close();

			for(unsigned int i = 0; i < size; i++) {
				vector<unsigned int> neighbors = getNeighbors(i);
				for(unsigned int j = 0; j < neighbors.size(); j++) {
					bool free = false;
					for(unsigned int k = 0; k < graph[i].size(); k++) {
						if(graph[i][k] == neighbors[j]) {
							free = true;
							break;
						}
					}
					if(!free) {
						blocked[i].push_back(neighbors[j]);
					}
				}
				sort (blocked[i].begin(), blocked[i].end());
			}
		}
		else {
			cerr << "Unable to open file";
		}
	}

	void print() const {
		cout << width << " x " << height << "\n";
		cout << "start: " << start << "\n";
		cout << "goal: " << goal << "\n";
		for(unsigned int i =0; i < graph.size(); i++) {
			cout << "node " << i << " -> {";
			for(unsigned int j =0; j < graph[i].size(); j++) {
				if(j < (graph[i].size() - 1))
					cout << graph[i][j] << ", ";
				else
					cout << graph[i][j];
			}
			cout << "}\n";
			cout << "node " << i << " !-> {";
			for(unsigned int j =0; j < blocked[i].size(); j++) {
				if(j < (blocked[i].size() - 1))
					cout << blocked[i][j] << ", ";
				else
					cout << blocked[i][j];
			}
			cout << "}\n";
		}
	}

	bool atGoal() const {
		return location == goal;
	}

	bool swapStartAndGoal() {
		unsigned int temp = start;
		start = goal;
		goal = temp;
	}

	bool updatePosition(string move) {
		unsigned int x = location % width;
		unsigned int y = location / width;

		unsigned int n = x + (y+1)* width;
		unsigned int s = x + (y-1)* width;
		unsigned int w = x+1 + (y * width);
		unsigned int e = x-1 + (y * width);

		unsigned int loc;

		if(move.compare("NORTH") == 0) loc = n;
		else if(move.compare("SOUTH") == 0) loc = s;
		else if(move.compare("WEST") == 0) loc = w;
		else if(move.compare("EAST") == 0) loc = e;
		else return false;

		for(unsigned int i = 0; i < blocked[location].size(); i++)
			if(loc == blocked[location][i])
				return false;

		location = loc;

		return true;
	}

	vector <string> getFreeNeighborStrings() const {
		vector <string> strings;

		unsigned int x = location % width;
		unsigned int y = location / width;

		unsigned int n = x + (y+1)* width;
		unsigned int s = x + (y-1)* width;
		unsigned int w = x+1 + (y * width);
		unsigned int e = x-1 + (y * width);

		for(unsigned int i = 0; i < graph[location].size(); i++)
			if(n == graph[location][i]) strings.push_back("NORTH");
			else if(s == graph[location][i]) strings.push_back("SOUTH");
			else if(w == graph[location][i]) strings.push_back("WEST");
			else if (e == graph[location][i]) strings.push_back("EAST");

		return strings;
	}

	vector <string> getBlockedNeighborStrings() const {
		vector <string> strings;

		unsigned int x = location % width;
		unsigned int y = location / width;

		unsigned int n = x + (y+1)* width;
		unsigned int s = x + (y-1)* width;
		unsigned int w = x+1 + (y * width);
		unsigned int e = x-1 + (y * width);

		for(unsigned int i = 0; i < blocked[location].size(); i++)
			if(n == blocked[location][i]) strings.push_back("NORTH");
			else if(s == blocked[location][i]) strings.push_back("SOUTH");
			else if(w == blocked[location][i]) strings.push_back("WEST");
			else if (e == blocked[location][i]) strings.push_back("EAST");

		return strings;
	}

	vector <unsigned int> getFreeNeighbors() const { return graph[location]; }
	vector <unsigned int> getBlockedNeighbors() const { return blocked[location]; }
	unsigned int getLocation() const { return location; }

private:

	vector<unsigned int> getNeighbors(unsigned int loc) const {
		vector<unsigned int> neighbors;

		int x = loc % width;
		int y = loc / width;

		if((x+1) < width) neighbors.push_back(x+1 + (y * width));
		if((x-1) >= 0) neighbors.push_back(x-1 + (y * width));
		if((y+1) < height) neighbors.push_back(x + (y+1)* width);
		if((y-1) >= 0 ) neighbors.push_back(x + (y-1)* width);

		return neighbors;
	}

	vector< vector<unsigned int> > graph;
	vector< vector<unsigned int> > blocked;
	unsigned int width, height, size, start, goal, location;
};
